LeetCode 75 Level 1 - Day 5 Greedy

121. Best Time to Buy and Sell Stock

• 題目連結
• 難易度：Easy

題目敘述

You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

預設函數

int maxProfit(int* prices, int pricesSize){

}

題目限制

解題過程及程式碼

本題是Greedy這個主題的第一題，給一個陣列表示股票每天的價格，選一天買再選一天賣，要找出獲利最大的買賣方式，一開始想法使用雙迴圈計算所有可能獲利情況，但是所花費的時間太長。

• 程式碼v1

  int maxProfit(int* prices, int pricesSize){
      int max_profit = 0;
      int temp_profit = 0;
      int i, j;
  
      for (i=0; i<pricesSize-1; i++) {
          for (j=i+1; j<pricesSize; j++) {
              temp_profit = prices[j] - prices[i];
              if (temp_profit <= 0) {
                   break;
              }
              if (temp_profit >= max_profit) {
                  max_profit = temp_profit;
              }
          }
      }
      return max_profit;
  }
  

後來想到遍歷一次陣列找到最小值和最大值，但是最大獲利不等於最大值-最小值 (先低買後高賣才可以得到最多錢)，若是最大值發生在最小值前面的天數所得出來的獲利就不合理了。

最後參考網路上的解法，發現和找最大值、最小值方法比較接近，同樣是遍歷一次，從第一天開始遇到價錢更低的就買下，接著後面一直檢查獲利是否為最大，雙迴圈方法的盲點在很多組合根本不需要計算，如下圖所示。

• 程式碼v2

  int maxProfit(int* prices, int pricesSize) {
      int min_price;
      int max_profit = 0;
      int i;
  
      min_price = prices[0];
  
      for (i=1; i<pricesSize; i++) {
          if (prices[i] < min_price) {  // 有更低的價錢就買下
              min_price = prices[i];
          }
  
          if ((prices[i] - min_price) > max_profit) {  // 獲利變大了就更新獲利
              max_profit = prices[i] - min_price;
          }
      }    
      return max_profit;
  }
  

第九天到這邊，謝謝大家。